1. Field of the Invention
My invention relates to the manipulation of time-ordered lists in multiple processing units or multiple programmed computing systems, and more particularly to enable the addition or deletion of items without a locking mechanism, even when multiple processing units have asynchronous access to the lists. It also includes novel computer instructions for performing the list manipulations.
2. Background Art
My invention deals with both queues as well as stacks. In a queue, also termed a FIFO (first-in, first-out) list, the first item added to the list is the first to be removed. In a stack, also termed a LIFO (last-in, first-out) list, the last item added to the list is the first to be removed. Asynchronous manipulation of FIFO and LIFO lists is very common in operating system and sub-systems environments. The limitations imposed on these environments by the inability to quickly and easily manipulate time-ordered lists are becoming excessive. As the number of processors used in tightly coupled complexes continues to increase, the cost of serialization by software will also increase. Because of the high utilization of time-ordered lists, this cost is becoming prohibitively expensive.
Currently, there are two common methods of maintaining a FIFO list. For a single headed queue, the list is defined as having one anchor point, all elements are added using this point and are deleted by searching down the list and removing the last element. This method allows for multiple adders, but only a single deleter. It also requires that the deleter search to the end of the list, which may cause the deleter to be interrupted by page faults. The overhead associated with page faults that may be incurred can become excessive with long lists.
For a double headed queue, the list is defined as having two anchor points, and all elements are added using one point and deleted using the other. This second method only allows one adder or deleter to be accessing the list at a time. To assure that only one access is allowed at a time, some method of serialization (a locking mechanism) must be employed.
The first method may be impractical because of the performance implications of excessive paging. The second method has the restriction that a lock must be used; this requirement can also contribute to performance degradation.
Other specific examples of prior art systems and method include U.S. Pat. Nos. 4,394,727 and 4,320,455, and the article by Conroy in the IBM Technical Disclosure Bulletin, Vol. 24, November 1981, pages 2716 to 2723, all of which involve the use of a lock bit or lock word.
One technique for avoiding the use of locking mechanisms in some instances in multi-processing or multiprogrammed computing systems is described in U.S. Pat. No. 3,886,525, which is assigned to the same assignee as the present application.
The then novel technique described in U.S. Pat. No. 3,886,525 included the invention of a new instruction at that time called "Compare and Swap." Using this instruction, each user of shared data is permitted to access it at its addressable location in the shared data store for further processing by the sequence of program instructions. After processing, the processed data is to be returned to the address location of the shared data. Prior to returning the processed data to the address location in the share data store, the new instruction is accessed in the sequence of instructions. Using "Compare and Swap," the data content of the addressed location accessed by the instruction is compared with the data accessed from the addressed location prior to the processing. As a result of this comparison, it can be determined that during the period of processing on the shared data, another user has or has not also accessed the shared data for processing, and returned a different value of the shared data back to the addressed storage location. If, in response to the Compare and Swap (CS) instruction, it is determined that the value of the addressed location has been modified by another user, the modified value is retained by the user and the processing is reinitiated on the modified value. If the value of the data in the addressed location accessed by the CS instruction is still identical to the value of the data accessed by the user prior to processing, it can be determined that no other user had accessed shared data and modified it. Therefore, the processed data will be transferred to the addressed location and further processing permitted (see Col. 2, line 8-39 of U.S. Pat. No. 3,886,525).
The COMPARE AND SWAP (CS) and its companion COMPARE DOUBLE AND SWAP (CDS) instructions are now used in multi-programming and multi-processing environments to serialize access to counters, flags, control words and other common storage areas. The IBM System/370 Extended Architecture Principles of Operation, (IBM Publication No. SA22-7085-0), hereinafter referred to as the 370XA Prin. Ops on page A45, gives the following example of providing for multiple asynchronous unlocked adders and deleters. It is identified as Table I. The list comprises a standard S/370 program segment which is well known to those skilled in the art as 370 Assembler Language. The first column lists mnemonic labels, the second column is the operation or instruction field, the third column lists the operand field and the fourth column contains comments. This is a standard format well known to those of skill in the art.
TABLE I ______________________________________ (Prior Art) ______________________________________ ADD TO FREE LIST Routine Initial Conditions: GR2 contains the address of the element to be added. GR4 contains the address of the header. 1. ADDQ LM 0,1,0(4) GR0,GR1 = contents of the header 2. TRYAGN ST 0,0(2) Point the new element to the top of the list 3. LR 3,1 Move the count to GR3 4. BCTR 3,0 Decrement the count 5. CDS 0,2,0(4) Update the header 6. BC 7,TRYAGN DELETE FROM FREE LIST Routine 7. DELETEQ LM 2,3,0(4) GR2,GR3 = contents of the header 8. TRYAGN LTR 2,2 Is the list empty? 9. BC 8,EMPTY Yes, get help 10. L 0,0(2) No, GR0 = the pointer from the first element 11. LR 1,3 Move the count to GR1 12. CDS 2,0,0(4) Update the header 13. BC 7,TRYAGN Update the header 14. USE (Any Instruction) The address of the removed element is in ______________________________________ Copyright .COPYRGT. IBM Corp. 1983
Probably the most significant point to note is that functions can be performed by programs running enabled for interruption (multiprogramming) or by programs that are running on a multi-processing configuration. In other words, the instructions CS and CDS allow a program to modify the contents of a storage location while running enabled, even though the routine may be interrupted by another program on the same CPU that will update the location, and even though the possibility exists that another CPU may simultaneously update the same location.
The CS instruction first checks the value of a storage location and then modifies it only if the value is what the program expects; normally, this would be a previously fetched value. If the value in storage is not what the program expects, then the location is not modified; instead, the current value of the location is loaded into a general register in preparation for the program to loop back and try again. During the execution of CS, no other CPU can access the specified location.
When a common storage area larger than a doubleword is to be updated, it is usually necessary to provide special interlocks to ensure that a single program at a time updates a common area. Such an area is called a serially reusable resource (SRR). In general, updating a list or even scanning a list, cannot be safely accomplished without locking the list. However, the CS instructions can be used in certain restricted situations to perform the lock/unlock functions and to provide sufficient queuing to resolve contentions, either in a LIFO or FIFO manner. A lock/unlock function can then be used as the interlock mechanism for updating an SRR of any complexity.
The lock/unlock functions are based on the use of a "header" associated with the SRR. The header is the common starting point for determining the states of the SRR, either free or in use, and also is used for queuing requests when contentions occur. Contentions are resolved using WAIT and POST. The general programming technique requires the program that encounters a "lock" SRR must "leave a mark on the wall," indicating the address of an ECB on which it will WAIT. The "unlocking program" sees the mark and POSTS the ECB, thereby permitting the WAITING program to continue. In most cases, all programs using a particular SRR must use either the LIFO queuing scheme or the FIFO scheme; the two are not mixed. When more complex queuing is required, the suggestion in the 370 XA Prin. Ops. manual is that the queue for the SRR delocks using one of the two methods shown.
As notes, the CS & CDS instructions have been used quite successfully. They enable users to obtain access to shared data or headers for the purpose of further processing. The need to prevent access to the addressed location when another user is processing data is eliminated by the CS instruction. However, the CS and CDS instructions apply only to a single word or a double word.
In contrast, as will be explained, the Compare and Swap Disjoint (CSD) and Compare and Load (CAL) instructions of my invention enable the referencing of two non-adjacent words (or double words in an expanded version).